CLA以及bit乘法

tags: IT鐵人

例題答案

就簡單把答案打出來囉~
小心轉換成二位元不要粗心。

Full Adder

在介紹Carry Lookahead Adder(CLA)之前，先跟各位介紹甚麼是Full Adder。

簡單來說長這樣	複雜一點長這樣	Logic Gate的表

|

與Full Adder相對的是Half Adder，後者沒有Carry-in，也就是說沒辦法接收前一個位元結果進位與否，因為晚點會用到的是Full Adder，在這邊就不介紹另一個了。

Full Adder接收兩個bit以及一個Carry-in，然後能夠輸出加法的結果以及進位。

CLA

CLA要達成的做法是避免每個Full Adder都要等前面一個把結果輸出才能開始做加法，如果我們能提前知道前面是否會進位，就能夠提前讓後面的Full Adder開始運作了，為了加速，我們就需要來一點邏輯遊戲了。

G & P

我們先定義兩個新東西，稱為Generate ( G ) & Propagate ( P )，概念上代表我是否產生進位以及我是否傳遞我收到的進位。

假設有四個Full Adder，F0的G為1，代表F0產生了進位，所以F1會收到進位，當F1的P=1，代表F1會繼續傳遞這個F0產生的進位到F2，以此類推，直到有人不傳遞也不產生，就會留在那邊，否則會繼續傳下去。

如此一來G和P的邏輯可以定義成：

g~i~ = a~i~ * b~i~
p~i~ = a~i~ + b~i~ (也可以用 a~i~ {xor} b~i~)

Combine

根據剛剛提到的傳遞方式，我們可以將每個Full Adder的進位寫成：

c~i~ = g~i-1~ + p~i-1~ * c~i-1~ , 1<=i<=4
其中Ci代表第i個Full Adder收到的Carry-in。
因為基本上都是以4位元的CLA實作，所以C~4~代表最後輸出給下一組的Carry-in

而每一組都可以把c展開來，化簡過程以及c的結果如下：

化簡過程及結果	CLA示意圖

如此一來我們就能在Full Adder算完之前拿到p,g，並且讓後面的Full Adder提早動作。

位元乘法

做直式乘法的時候，我們需要一個一個用九九乘法表計算，把進位加進去，並且把每個位數做完後加起來，不過因為電腦使用二進位制，0和1的意思分別代表填0或是把被乘數照抄，這就是電腦的運算方式。

電腦運算的時候，是將被乘數每次往左邊shift一格，代表乘法一次比一次還要大一個位元，類似平常直式乘法每次都會比上一個從更前面的地方開始運算。

而乘數會每次往右邊shift一格，代表做完之後丟掉，把下一個要計算的位元移動到準備計算的位置。

如下：

不過因為數字都是32bit，而結果最大是64bit，並且在前面幾次的乘法並不會壓滿64bit，所以為了節省空間，我們可以先將Product以及Multiplier寫在一起，把不會改變的被乘數固定32bit，每次決定乘法結果時，和Product的最大32bit加起來填回去並且向右shift一位。

如下：

如此一來就能夠同時縮小成本及空間，少了乘數的空間、被乘數又縮短成32bit，並且只要32bit的ALU，可以說是一石多鳥阿！！

這次的內容比較難出題目，那我們就地解散ㄅ，88~